package leetcode_900;

/**
 *@author 周杨
 *StoneGame_877 一排数组 有A和B玩游戏 每次选择一个元素 数组是偶数 问最终谁的分高
 *describe:用动态规划 AC 24%
 *2018年11月8日 下午12:35:43
 */
public class StoneGame_877 {
	int dp[][][][];
	
	
	/**
	 * describe:动态规划 AC 24%
	 * 2018年11月8日 下午12:35:24
	 */
	public boolean stoneGame(int[] piles) {
		int dp[][]=new int[piles.length][piles.length];
		memory(piles, 0, piles.length-1, dp);
        return dp[0][piles.length-1]>0;
    }
	
	public int  memory(int []piles,int left,int right,int dp[][]) {
		if(dp[left][right]!=0)
			return dp[left][right];
		if(left==right-1) {//最后一轮选择
			dp[left][right]=Math.abs(piles[left]-piles[right]);
		}
		else {
			if((right-left)%2==1) {//偶数  轮到Alex选择
				dp[left][right]=Math.max(piles[left]+memory(piles, left+1, right, dp),
						piles[right]+memory(piles, left, right-1, dp));
			}
			else {
				dp[left][right]=Math.min(piles[left]+memory(piles, left+1, right, dp),
						piles[right]+memory(piles, left, right-1, dp));
			}
		}
		return dp[left][right];
	}
	
	
	
	/**
	 * describe:如果深搜会超时 增加4维dp会出现空间超时
	 * 2018年11月8日 下午12:00:31
	 */
	public boolean stoneGame1(int[] piles) {
		this.dp=new int [piles.length][piles.length][500*piles.length][500*piles.length];
        return help(piles,0,piles.length-1,0,0);
    }
	
	//Alex开始 偶数 
	public boolean help(int []piles,int left,int right,int sum1,int sum2) {
		if(dp[left][right][sum1][sum2]!=0) {
			return dp[left][right][sum1][sum2]==1?true:false;
		}
		boolean flag=false;
		if(left==right-1) {//最后一轮选择
			if(piles[left]>piles[right]) {
				flag= sum1+piles[left]>sum2+piles[right];
				dp[left][right][sum1][sum2]=flag?1:2;
				return flag;
			}
			else {
				flag= sum1+piles[right]>sum2+piles[left];
				dp[left][right][sum1][sum2]=flag?1:2;
				return flag;
			}
		}
		else {
			if((right-left)%2==1) {//偶数  轮到Alex选择
				flag= help(piles,left+1,right,sum1+piles[left],sum2)||
						help(piles,left,right-1,sum1+piles[right],sum2);
				
				dp[left][right][sum1][sum2]=flag?1:2;
				return flag;
			}
			else {
				flag= help(piles,left+1,right,sum1,sum2+piles[left])||
						help(piles,left,right-1,sum1,sum2+piles[right]);
				
				dp[left][right][sum1][sum2]=flag?1:2;
				return flag;
			}
		}
	}
}
